package HelloAlgo.va;

/**
 * @author jing
 * @BelongsProject: JavaDataStructure
 * @CreateTime: 2025-03-07  17:42
 * @Description: 给定一个数，判断从1到这个数之间有多少个素数，素数是只能被1和本身整除的数，1不是素数
 * @Version: 1.0
 */
public class _002PrimeNumberPlus {
    public static void main(String[] args) {
        System.out.println(eratosthenes(100));
    }


    public static int eratosthenes(int n){
        boolean[] isPrime = new boolean[n]; //false表示是素数
        int count = 0;
        for(int i = 2; i<n; i++){
            if(!isPrime[i]){
                count++;
                for(int j = i*i;j<n;j+=i){
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }
}
